package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:链表插入排序
 * author: Mr.Du
 * Date: 2022/11/17
 * Time: 20:37
 */
public class InsertionSortList {
    
    /**
     * 画图
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1,head);
        ListNode p1 = dummy;
        ListNode c = head.next;
        while(head != null && head.next != null){
            if(head.val < head.next.val){
                head = head.next;
                continue;
            }
            while(p1.next.val < head.next.val){
                p1 = p1.next;
            }
            ListNode tmp = head.next;
            head.next = tmp.next;
            tmp.next = p1.next;
            p1.next = tmp;
            p1 = dummy;
        }
        return dummy.next;
    }
}
